package main.bytedance.FS;

import java.util.Deque;
import java.util.LinkedList;

/**
 *深度优先遍历(递归实现)
 * 实现思路：
 * 1.先拿到每个节点，进入查找时如果时0或者已经在横竖范围之外了，就直接为0
 * 2.只有非0的才会进入到寻找的过程，拿到这个节点，先把它置为0，这样再下次遍历递归时就可以直接返回了
 * 3.置为0之后，拿上下左右的，再取递归，碰到一个为0的就可以直接返回了，不用再往一个方向寻找了
 * 4.取上下左右之和也就是岛屿的面积了，因为它找到的是上下左右，置为0的不用担心和其他的还有关系。
 * 5.因为之前有一个非0的需要+1
 * 复杂度为O(C*R)c是行是列
 * @author kejl
 * @version test
 * @date 2020/5/28 17:55
 */
public class MaxAreaOfIsland {

   static int count = 0;
    public static void main(String[] args) {

        int[][] dd = {  {0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,0,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,0,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};

        System.out.println(dd.length);
      int a =   new MaxAreaOfIsland().maxAreaOfIsland(dd);
      System.out.println(count);
    }


    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                //计算最大面积
                int currMaxArea = getMaxArea(i, j, grid);
                maxArea = Math.max(currMaxArea, maxArea);
            }
        }

        return maxArea;
    }

    private int getMaxArea(int i, int j, int[][] grid) {
        count ++;
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        //通过将经过的岛屿设置为0来确保下次不会重复访问
        grid[i][j] = 0;

        int upMaxArea = getMaxArea(i - 1, j, grid);

        int downMaxArea = getMaxArea(i + 1, j, grid);

        int leftMaxArea = getMaxArea(i, j - 1, grid);

        int rightMaxArea = getMaxArea(i, j + 1, grid);

        return upMaxArea + downMaxArea + leftMaxArea + rightMaxArea + 1;
    }


    /**
     * 深度优先遍历(栈实现)
     * 1.算法和上一个类似，只不过是把下一个的元素使用{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}获取
     * 2.放到了栈里面，然后再循环遍历
     * @param grid
     * @return
     */
    public int maxAreaOfIsland2(int[][] grid) {
        Deque<int[]> stack = new LinkedList<>();

        int[][] moveIndexArray = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                stack.push(new int[]{i, j});
                //计算最大面积
                int currMaxArea = 0;
                while (!stack.isEmpty()) {
                    int[] pop = stack.pop();
                    int currI = pop[0];
                    int currJ = pop[1];
                        if (currI < 0 || currI >= grid.length || currJ < 0 || currJ >= grid[0].length || grid[currI][currJ] == 0) {
                            continue;
                    }
                    currMaxArea++;
                    grid[currI][currJ] = 0;
                    for (int[] moveIndex : moveIndexArray) {
                        stack.push(new int[]{currI + moveIndex[0], currJ + moveIndex[1]});//放入的是下一个节点的位置，来进行循环
                    }
                }
                maxArea = Math.max(currMaxArea, maxArea);
            }
        }
        return maxArea;
    }

    /**
     * 上个写法类似
     * @param grid
     * @return
     */
    public int maxAreaOfIsland3(int[][] grid) {
        Deque<int[]> queue = new LinkedList<>();

        int[][] moveIndexArray = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                queue.offer(new int[]{i, j});
                //计算最大面积
                int currMaxArea = 0;
                while (!queue.isEmpty()) {
                    int size = queue.size();
                    for (int k = 0; k < size; k++) {
                        int[] poll = queue.poll();
                        int currI = poll[0];
                        int currJ = poll[1];
                        if (currI < 0 || currI >= grid.length || currJ < 0 || currJ >= grid[0].length || grid[currI][currJ] == 0) {
                            continue;
                        }
                        currMaxArea++;
                        grid[currI][currJ] = 0;
                        for (int[] moveIndex : moveIndexArray) {
                            queue.offer(new int[]{currI + moveIndex[0], currJ + moveIndex[1]});
                        }
                    }
                }
                maxArea = Math.max(currMaxArea, maxArea);
            }
        }

        return maxArea;
    }

}
